#include <stdio.h>

/*此处是顺序队列数据结构定义*/
typedef int DataType;
struct seqQueue//请完成数据结构定义
{
    int MAXIMUM;
    int front;
    int rear;
    DataType * data;
};

typedef struct seqQueue *PseqQueue;
//第一关
PseqQueue createNullQueue_seq(int m)
{//此处填写代码，创建一个空的顺序队列，能存放的最大元素个数为 m
 //若m=0，则返回NULL 
    if (0 == m)
        return NULL;
    PseqQueue q = (PseqQueue)malloc(sizeof(struct seqQueue)); 
    if (NULL == q) {
        printf("Out of Space!\n");
        return NULL;
    }
    q->data = (DataType *)malloc(sizeof(DataType)*(m+1));
    if (NULL == q->data) {
        printf("Out of Space!\n");
        return NULL;
    }
    q->MAXIMUM = m;
    q->front = 0;
    q->rear = 0;
    return q;
}

//第二关
int isNullQueue_seq(PseqQueue Q)
{
  //判断顺序（环形）队列是否为空，若为空，返回值为1，否则返回值为0,若队列不存在，则返回-1
    if (NULL == Q || NULL == Q->data)
        return -1;
    else if (Q->front == Q->rear)
        return 1;
    else 
        return 0;
}


//第三关 
int isFullQueue_seq(PseqQueue Q)
{
  //判断环形队列是否已满，若已满，返回值为1，否则返回值为0
    if (NULL == Q || NULL == Q->data)
        return 0;
    else if ((Q->rear+1)%(Q->MAXIMUM+1) == Q->front)
        return 1;
    else 
        return 0;
}


//第四关
int enQueue_seq(PseqQueue Q ,DataType x)
{//在环形队列中插入数据元素x，若插入不成功，返回0；插入成功返回值为1
    if (1 == isFullQueue_seq(Q))
        return 0;
    Q->data[(Q->rear++)%(Q->MAXIMUM+1)]=x;
    return 1;
}
 


//第五关
DataType delQueue_seq(PseqQueue Q)
{//出队并返回删除元素，若队列为空，则返回-1
    if (0 != isNullQueue_seq(Q))
        return -1;
    return Q->data[(Q->front++)%(Q->MAXIMUM+1)];
}

//第六关
DataType front_seq(PseqQueue Q)
{// 取队首元素返回，若队列为空，则返回-1
    if (0 != isNullQueue_seq(Q))
        return -1;
    return Q->data[Q->front];
}

//销毁顺序队列，释放队列所占存储空间
int destroyQueue_seq(PseqQueue Q)
{
    //返回值为销毁的栈中现有数据元素的个数，若待销毁的线性表不存在，则返回0
    if (-1 == isNullQueue_seq(Q))
        return 0;
    int num = (Q->rear - Q->front) % Q->MAXIMUM + 1;
    free(Q->data);
    Q->data = NULL;
    free(Q);
    return 0;
}


//第七关
void queueApp(int a[],int n)
{
//参数用于传递顾客编号和顾客人数，输出顾客接受服务后离开顺序
    PseqQueue QA = createNullQueue_seq(n);
    PseqQueue QB = createNullQueue_seq(n);
    for (int i = 0; i < n; i++)
        if (a[i] % 2 == 0)
            enQueue_seq(QB, a[i]);
        else
            enQueue_seq(QA, a[i]);
    while(!isNullQueue_seq(QA) || !isNullQueue_seq(QB)) {
        for (int i = 0; i < 2 && !isNullQueue_seq(QA); i++)
            printf("%d ", delQueue_seq(QA));
        if(!isNullQueue_seq(QB))
            printf("%d ", delQueue_seq(QB));
    }

}









